package leetcode_day._2022._202210._2131;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 901. 股票价格跨度
 * 算法：单调栈
 * 使用单调栈保证单调递减
 * 栈存的元素是一个带有两个元素的数组, 第一个元素表示 price, 第二个元素表示当前 price 的跨度
 * 如果栈为空或者栈顶的 price 大于当前的 price, 直接入栈
 * 反之, 则出栈, 直到栈顶元素的 price 大于当前 price
 *
 * @author yezh
 * @version 1.0
 * @date 2022/10/21 23:53
 */
public class _21_901 {

    class StockSpanner {

        Deque<int[]> stack;

        public StockSpanner() {
            stack = new ArrayDeque<>();
        }

        public int next(int price) {
            int day = 1;
            while (!stack.isEmpty() && price >= stack.peek()[0]) day += stack.pollFirst()[1];
            stack.addFirst(new int[]{price, day});
            return day;
        }
    }

}
